 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> trees/rb_tree.h                                                                         *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#ifndef DS_RB_TREE
#define DS_RB_TREE

#include "ds.h"
#include "trees/bin_tree.h"

/* each node has red or black color */
typedef enum rb_color_t {
  RBT_CBLACK = 0,
  RBT_CRED,
  RBT_CEMPTY /* if node is empty */
} rb_color_t;

/* red-black tree specific structure */
struct _rb_pvt {
  int bh;           /* black height of tree */
  rb_color_t color; /* node color */
};

typedef struct rb_tree {
  struct _bit* tree;
  BIT_DEFAULT_FUNCS(struct rb_tree);
  /* some extra functions: */
  int (*node_get_bh)(const bit_node*);
  rb_color_t (*node_get_color)(const bit_node*);
} rb_tree;

#define bit2rb_tree(tree)						\
  BIT_CONVERTION(tree, rb_tree)

rb_tree* rb_create(void);
rb_tree* rb_join(rb_tree*, rb_tree*);
rb_tree* rb_split(rb_tree*, bit_node*);
void rb_destroy(rb_tree*);

#endif /* DS_RB_TREE */
